//https://leetcode.cn/problems/design-linked-list/
package codeRandomThoughts.Test707设计链表;

//先给出链表中的节点类
class ListNode {
    public int val;
    public ListNode next;

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    public ListNode() {
    }

    public ListNode(int val) {
        this.val = val;
    }

}

class MyLinkedList {

    private ListNode head;

    private int length;

    public MyLinkedList() {
        this.length = 0;
        this.head = new ListNode();
    }

    public int get(int index) {
        if (index < 0 || index > length - 1) {
            return -1;
        } else {
            ListNode curr = head;
            for (int i = 0; i < index + 1; i++) {
                curr = curr.next;
            }
            return curr.val;
        }
    }

    public void addAtHead(int val) {
        this.addAtIndex(0, val);
    }

    public void addAtTail(int val) {
        this.addAtIndex(length, val);
    }

    /**
     * 在链表中的第index个节点之前添加值为val的节点。
     * 如果index等于链表的长度，则该节点将附加到链表的末尾。
     * 如果 index 大于链表长度，则不会插入节点。
     * 如果index小于0，则在头部插入节点。
     */
    public void addAtIndex(int index, int val) {
        if (index > this.length) {
            return;
        } else if (index < 0) {
            //addAtIndex(0, val);
            index = 0;//这样写是真划算
        } else {
            ListNode curr = head;
            for (int i = 0; i < index; i++) {
                curr = curr.next;
            }

            ListNode toAdd = new ListNode(val);
            toAdd.next = curr.next;
            curr.next = toAdd;
            this.length++;
        }
    }

    public void deleteAtIndex(int index) {
        if (index >= 0 && index < length) {
            ListNode curr = head;
            for (int i = 0; i < index; i++) {
                curr = curr.next;
            }
            curr.next = curr.next.next;
            this.length--;
        }

    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */